Packet switching communications networks such as asynchronous transfer mode (ATM) communication networks are typically made up of a number of communication nodes coupled for communication over a set of high speed communication links. Such a communication network usually enables communication among a wide variety of communication devices including video, voice, data and facsimile devices. The topology of such a communication network typically enables the establishment of a variety of communication paths between any two communication nodes in the network. Such a communication path is generally referred to as a virtual circuit in the communication network. Typically, a physical path though the communication nodes for such a virtual circuit is established according to bandwith utilization requirements for the virtual circuit and the available resources in the communication nodes and on the high speed communication links. The communication nodes discussed above often perform cell switching, that is, routing cells from one end-point to another, across the virtual circuits. Typically, these nodes or switches are made up of a number of port cards, with each card having circuitry for performing cell switching operations. Cells are passed between cards (i.e., between ports) over a system bus which interconnects each of the cards.
In many switches, there are multiple, memory-less, lanes for cells to take between two cards of the switch. In general, each card will have appropriate circuitry for transmitting and receiving cells across the cell lanes and for interfacing with the high speed transmission links of the communication network. FIG. 1 illustrates such a communication switch 10.
Communication switch 10 includes two cards 20, each of which are coupled to a cell bus 22 which is made up of four cell transmission lanes. Each card 20 is also coupled to a high speed transmission link 24. Those skilled in the art will appreciate that cards 20 include circuitry necessary for transmission and reception of ATM cells across cell bus 22 and across high speed links 24. In particular, as is typical of ATM switches such as switch 10, cards 20 include transmit and receive buffers 26 (for clarity only one transmit and receive buffer 26 is labeled, however, all are substantially similar).
For a single virtual circuit passing through switch 10, the order of cells appearing on the input must be preserved at the output. This is because ATM is a connection oriented scheme and no provision is made in the associated protocols for cell reordering. In switch 10, a card 20 is granted access to the cell bus 22 shortly before cell transmission is to start. Because ATM is asynchronous in nature, at this grant time there may be from zero to n (n=number of cell lanes) cells that could be sent during this transmit opportunity. For the example illustrated in FIG. 1 where cell bus 22 has 4 cell lanes, there may be from 0 to 4 cells that could be sent during a transmission opportunity. As multiple cells need to be sent in parallel, a card 20 may unload each of its first-in-first-out (FIFO) buffers 26 into an appropriate cell lane of cell bus 22 when the transmit opportunity occurs. However, this method of preparing multiple cells for transmission across the cell bus 22 presents the possibility of reordering cells on a particular virtual circuit.
For example, consider the switch design where cells are loaded as they are received from a high speed communication link 24 into four cell lane FIFOs 26 of a card 20 on a round robin basis. Suppose cells n and n+1 for a particular virtual circuit are received and are loaded into the first two cell lane FIFOs 26 for transmission on cell bus 22. Further suppose that just as cell n+2 is arriving on high speed communication link 24, a transmit opportunity for the card 20 arrives. Those skilled in the art will appreciate that these transmit opportunities are governed by a cell bus arbiter which controls access to cell bus 22 by multiple cards 20. When the transmit opportunity arrives, cells n and n+1 will be sent over the cell bus 22 to a destination card. If cell n+2 is then loaded into the lane 3 FIFO (because the FIFOs associated with lanes 1 and 2 were full just as cell n+2 arrived) then cell n+3, the next cell received over high speed communication link 24, is loaded into the cell lane 1 FIFO (because the contents of this FIFO have just been transmitted over cell bus 22). At the next transmit opportunity, if cells n+2 and cell n+3 are sent across cell bus 24, a destination card may think that cell n+3 came before cell n+2 since cell n+3 is now present on cell bus 22 lane 1. This would result in the ATM cells for single virtual connection being reordered at the destination card.
In order to prevent such a reordering, several alternatives exists. For example, a single virtual connection may be restricted to send cells only over a particular cell bus cell lane. However, this solution has several disadvantages. For instance, any particular virtual connection's bandwidth would be limited to that of a single cell lane. Also, extra circuitry and/or storage would be needed at each card 20 to keep track of the cell path assigned to each virtual connection.
Alternatively, extra ordering information (e.g., header information) within each cell on a cell path could be introduced. This could be thought of as tagging each cell with its order as it is placed onto a cell lane of cell bus 22. Using these tags, the receiving card 20 could sort out the order in which cells of a particular virtual connection were received. The disadvantage here is that the additional overhead required for the tags reduces the overall cell path bandwidth which is used for switching cells between cards.